package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * 558. 四叉树交集
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/12 16:03
 */
public class Intersect {

    public Node intersect(Node quadTree1, Node quadTree2) {
        return find(quadTree1, quadTree2, false);
    }

    private Node find(Node a, Node b, boolean value) {

        if (a == null && b == null) {
            return null;
        }

        Node no = new Node();
        if (a == null) {

            if (b.isLeaf && b.val) {
                no.isLeaf = true;
                no.val = true;
                return no;
            }
            if (b.isLeaf) {
                no.isLeaf = true;
                no.val = b.val || value;
            } else {
                no.isLeaf = false;
                no.topLeft = find(a, b.topLeft, value);
                no.topRight = find(a, b.topRight, value);
                no.bottomLeft = find(a, b.bottomLeft, value);
                no.bottomRight = find(a, b.bottomRight, value);
            }
            return no;
        }

        if (b == null) {
            if (a.isLeaf) {
                no.isLeaf = true;
                no.val = a.val || value;
            } else {
                no.isLeaf = false;
                no.topLeft = find(a.topLeft, b, value);
                no.topRight = find(a.topRight, b, value);
                no.bottomLeft = find(a.bottomLeft, b, value);
                no.bottomRight = find(a.bottomRight, b, value);
            }
            return no;
        }


        if ((a.isLeaf && a.val) || (b.isLeaf && b.val)) {
            no.isLeaf = true;
            no.val = true;
            return no;
        }
        value = a.isLeaf ? a.val : b.val;
        no.isLeaf = a.isLeaf && b.isLeaf;
        Node n1 = find(a.topLeft, b.topLeft, value);
        Node n2 = find(a.topRight, b.topRight, value);
        Node n3 = find(a.bottomLeft, b.bottomLeft, value);
        Node n4 = find(a.bottomRight, b.bottomRight, value);


        if (n1 != null && n2 != null && n3 != null && n4 != null) {
            if (n1.isLeaf && n2.isLeaf && n3.isLeaf && n4.isLeaf) {
                if (n1.val == n2.val && n2.val == n3.val && n3.val == n4.val) {
                    no.val = true;
                    no.isLeaf = true;
                    return no;
                }
            }
        }

        no.topLeft = n1;
        no.topRight = n2;
        no.bottomLeft = n3;
        no.bottomRight = n4;

        return no;
    }

    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;

        public Node() {
        }

        public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
            val = _val;
            isLeaf = _isLeaf;
            topLeft = _topLeft;
            topRight = _topRight;
            bottomLeft = _bottomLeft;
            bottomRight = _bottomRight;
        }
    }

}



